#include <iostream>
#include <string>
#include <vector>

#define _DEBUG_SELF

using namespace std;

class Solution {
public:
  string convert(string s, int numRows) {

    if (numRows == 1) {
      return s;
    }
    // get column
    int len = s.size();
    int row = numRows;
    int col = 0;

    col = len / (row + row - 2) * (row - 2 + 1);
    int res = len % (row + row - 2);
    res = res <= row ? 1 : (res % row) + 1;
    col += res;

    int idx = 0;
    vector< vector<int> > matrix(row, vector<int>(col, 0));
    for (int ci = 0; ci < col; ci++) {
      for (int ri = 0; ri < row; ri++) {
        if ((ci == 0) || (ci % (row - 1) == 0)) {
          matrix[ri][ci] = s[idx];
#ifdef _DEBUG_SELF
          printf("=idx:%d, [%d:%d], val:%c\n", idx, ri, ci, s[idx]);
#endif
          idx++;
          if (idx > len) { // overflow
            break;
          }
        } else {
          // only fill one
          int fillRi = row - 1 - (ci % (row - 1));
          matrix[fillRi][ci] = s[idx];
#ifdef _DEBUG_SELF
          printf("-idx:%d, [%d:%d], val:[%c]\n", idx, fillRi, ci, s[idx]);
#endif
          idx++;
          break;
        }
      }
    }

    string result = "";
    for (int ri = 0; ri < row; ri++) {
      for (int ci = 0; ci < col; ci++) {
        char x = matrix[ri][ci];
#ifdef _DEBUG_SELF
        if (x == 0) {
          printf("[ ] ");
        } else {
          printf("[%c] ", x);
        }
        if (ci == col - 1) {
          printf("\n");
        }
#endif
        if (x != 0) {
          result.push_back(x);
        }
      }
    }
    return result;
  }
};

/*

0 1 2 3 4
4 3 2 1 0
PAYPALISHIRING
==============
P     I    N
A   L S  I G
Y A   H R
P     I
==============


ci -> pos(ci)

pos(0) = fill
pos(1) = 2
pos(2) = 1
pos(3) = fill
pos(4) = 2
pos(5) = 1

row = 4

(row -1 ) - (ci %(row -1) ) = 3 - ci % 3




PAYPALISHIRING
==============
P   A   H   N
A P L S I I G
Y   I   R
==============
len: raw str total length
row: wait split row length
col: wait split column length

col ->
len / (row + (row - 2))
len % (row + (row - 2)) -> val <= row ? 1 : 2

arr[row][col]

sweep column
row up -> down

if ri % row == 0; fill

else
   fill row - ci


vector<vector<int>>
 */

void testcase01() {
  printf("\n\n");
  string input = "PAYPALISHIRING";
  string want = "PINALSIGYAHRPI";

  Solution so;
  string got = so.convert(input, 4);
  if (got != want) {
    printf("want:%s, but got:%s\n", want.c_str(), got.c_str());
  }
}
void testcase02() {
  printf("\n\n");
  string input = "PAYPALISHIRING";
  string want = "PAYPGANLIIRSIH";

  Solution so;
  string got = so.convert(input, 9);
  if (got != want) {
    printf("want:%s, but got:%s\n", want.c_str(), got.c_str());
  }
}

int main() {
  testcase01();
  testcase02();

  return 0;
}
